home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / lib / calc / zmath.h < prev   
C/C++ Source or Header  |  1995-07-17  |  12KB  |  345 lines
  1. /*
  2.  * Copyright (c) 1993 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Data structure declarations for extended precision integer arithmetic.
  7.  * The assumption made is that a long is 32 bits and shorts are 16 bits,
  8.  * and longs must be addressible on word boundaries.
  9.  */
  10.  
  11. #ifndef    ZMATH_H
  12. #define    ZMATH_H
  13.  
  14. #include <stdio.h>
  15. #include "alloc.h"
  16. #include "endian.h"
  17.  
  18. #include "have_stdlib.h"
  19. #ifdef HAVE_STDLIB_H
  20. # include <stdlib.h>
  21. #endif
  22.  
  23.  
  24. #ifndef ALLOCTEST
  25. # if defined(CALC_MALLOC)
  26. #  define freeh(p) (((void *)p == (void *)_zeroval_) ||            \
  27.             ((void *)p == (void *)_oneval_) || free((void *)p))
  28. # else
  29. #  define freeh(p) { if (((void *)p != (void *)_zeroval_) &&        \
  30.              ((void *)p != (void *)_oneval_)) free((void *)p); }
  31. # endif
  32. #endif
  33.  
  34.  
  35. typedef    short FLAG;            /* small value (e.g. comparison) */
  36. typedef int BOOL;            /* TRUE or FALSE value */
  37. typedef unsigned long HASH;        /* hash value */
  38.  
  39.  
  40. #if !defined(TRUE)
  41. #define    TRUE    ((BOOL) 1)            /* booleans */
  42. #endif
  43. #if !defined(FALSE)
  44. #define    FALSE    ((BOOL) 0)
  45. #endif
  46.  
  47.  
  48. /*
  49.  * NOTE: FULL must be twice the storage size of a HALF
  50.  *     LEN storage size must be <= FULL storage size
  51.  */
  52. typedef unsigned short HALF;        /* unit of number storage */
  53. typedef unsigned long FULL;        /* double unit of number storage */
  54. typedef long LEN;            /* unit of length storage */
  55.  
  56. #define BASE    ((FULL) 65536)        /* base for calculations (2^16) */
  57. #define BASE1    ((FULL) (BASE - 1))    /* one less than base */
  58. #define BASEB    16            /* number of bits in base */
  59. #define    BASEDIG    5            /* number of digits in base */
  60. #define    MAXHALF    ((FULL) 0x7fff)        /* largest positive half value */
  61. #define    MAXFULL    ((FULL) 0x7fffffff)    /* largest positive full value */
  62. #define    TOPHALF    ((FULL) 0x8000)        /* highest bit in half value */
  63. #define    TOPFULL    ((FULL) 0x80000000)    /* highest bit in full value */
  64. #define MAXLEN    ((LEN)    0x7fffffff)    /* longest value allowed */
  65. #define    MAXREDC    5            /* number of entries in REDC cache */
  66. #define    SQ_ALG2    20            /* size for alternative squaring */
  67. #define    MUL_ALG2 20            /* size for alternative multiply */
  68. #define    POW_ALG2 40            /* size for using REDC for powers */
  69. #define    REDC_ALG2 50            /* size for using alternative REDC */
  70.  
  71.  
  72.  
  73. typedef union {
  74.     FULL    ivalue;
  75.     struct {
  76.         HALF Svalue1;
  77.         HALF Svalue2;
  78.     } sis;
  79. } SIUNION;
  80.  
  81.  
  82. #if !defined(BYTE_ORDER)
  83. #include <machine/endian.h>
  84. #endif
  85.  
  86. #if !defined(LITTLE_ENDIAN)
  87. #define LITTLE_ENDIAN    1234    /* Least Significant Byte first */
  88. #endif
  89. #if !defined(BIG_ENDIAN)
  90. #define BIG_ENDIAN    4321    /* Most Significant Byte first */
  91. #endif
  92. /* PDP_ENDIAN - LSB in word, MSW in long is not supported */
  93.  
  94. #if BYTE_ORDER == LITTLE_ENDIAN
  95. # define silow    sis.Svalue1    /* low order half of full value */
  96. # define sihigh    sis.Svalue2    /* high order half of full value */
  97. #else
  98. # if BYTE_ORDER == BIG_ENDIAN
  99. #  define silow    sis.Svalue2    /* low order half of full value */
  100. #  define sihigh sis.Svalue1    /* high order half of full value */
  101. # else
  102.    :@</*/>@:    BYTE_ORDER must be BIG_ENDIAN or LITTLE_ENDIAN    :@</*/>@:
  103. # endif
  104. #endif
  105.  
  106.  
  107. typedef struct {
  108.     HALF    *v;        /* pointer to array of values */
  109.     LEN    len;        /* number of values in array */
  110.     BOOL    sign;        /* sign, nonzero is negative */
  111. } ZVALUE;
  112.  
  113.  
  114.  
  115. /*
  116.  * Function prototypes for integer math routines.
  117.  */
  118. #if defined(__STDC__)
  119. #define MATH_PROTO(a) a
  120. #else
  121. #define MATH_PROTO(a) ()
  122. #endif
  123.  
  124. extern HALF * alloc MATH_PROTO((LEN len));
  125. #ifdef    ALLOCTEST
  126. extern void freeh MATH_PROTO((HALF *));
  127. #endif
  128.  
  129.  
  130. /*
  131.  * Input, output, and conversion routines.
  132.  */
  133. extern void zcopy MATH_PROTO((ZVALUE z, ZVALUE *res));
  134. extern void itoz MATH_PROTO((long i, ZVALUE *res));
  135. extern void atoz MATH_PROTO((char *s, ZVALUE *res));
  136. extern long ztoi MATH_PROTO((ZVALUE z));
  137. extern void zprintval MATH_PROTO((ZVALUE z, long decimals, long width));
  138. extern void zprintx MATH_PROTO((ZVALUE z, long width));
  139. extern void zprintb MATH_PROTO((ZVALUE z, long width));
  140. extern void zprinto MATH_PROTO((ZVALUE z, long width));
  141.  
  142.  
  143. /*
  144.  * Basic numeric routines.
  145.  */
  146. extern void zmuli MATH_PROTO((ZVALUE z, long n, ZVALUE *res));
  147. extern long zdivi MATH_PROTO((ZVALUE z, long n, ZVALUE *res));
  148. extern long zmodi MATH_PROTO((ZVALUE z, long n));
  149. extern void zadd MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  150. extern void zsub MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  151. extern void zmul MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  152. extern void zdiv MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res, ZVALUE *rem));
  153. extern void zquo MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  154. extern void zmod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *rem));
  155. extern BOOL zdivides MATH_PROTO((ZVALUE z1, ZVALUE z2));
  156. extern void zor MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  157. extern void zand MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  158. extern void zxor MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  159. extern void zshift MATH_PROTO((ZVALUE z, long n, ZVALUE *res));
  160. extern void zsquare MATH_PROTO((ZVALUE z, ZVALUE *res));
  161. extern long zlowbit MATH_PROTO((ZVALUE z));
  162. extern long zhighbit MATH_PROTO((ZVALUE z));
  163. extern void zbitvalue MATH_PROTO((long n, ZVALUE *res));
  164. extern BOOL zisset MATH_PROTO((ZVALUE z, long n));
  165. extern BOOL zisonebit MATH_PROTO((ZVALUE z));
  166. extern BOOL zisallbits MATH_PROTO((ZVALUE z));
  167. extern FLAG ztest MATH_PROTO((ZVALUE z));
  168. extern FLAG zrel MATH_PROTO((ZVALUE z1, ZVALUE z2));
  169. extern BOOL zcmp MATH_PROTO((ZVALUE z1, ZVALUE z2));
  170.  
  171.  
  172. /*
  173.  * More complicated numeric functions.
  174.  */
  175. extern long iigcd MATH_PROTO((long i1, long i2));
  176. extern void zgcd MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  177. extern void zlcm MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  178. extern void zreduce MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *z1res, ZVALUE *z2res));
  179. extern void zfact MATH_PROTO((ZVALUE z, ZVALUE *dest));
  180. extern void zpfact MATH_PROTO((ZVALUE z, ZVALUE *dest));
  181. extern void zlcmfact MATH_PROTO((ZVALUE z, ZVALUE *dest));
  182. extern void zperm MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  183. extern void zcomb MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  184. extern BOOL zprimetest MATH_PROTO((ZVALUE z, long count));
  185. extern FLAG zjacobi MATH_PROTO((ZVALUE z1, ZVALUE z2));
  186. extern void zfib MATH_PROTO((ZVALUE z, ZVALUE *res));
  187. extern void zpowi MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  188. extern void ztenpow MATH_PROTO((long power, ZVALUE *res));
  189. extern void zpowermod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE z3, ZVALUE *res));
  190. extern BOOL zmodinv MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  191. extern BOOL zrelprime MATH_PROTO((ZVALUE z1, ZVALUE z2));
  192. extern long zlog MATH_PROTO((ZVALUE z1, ZVALUE z2));
  193. extern long zlog10 MATH_PROTO((ZVALUE z));
  194. extern long zdivcount MATH_PROTO((ZVALUE z1, ZVALUE z2));
  195. extern long zfacrem MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *rem));
  196. extern void zgcdrem MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  197. extern long zlowfactor MATH_PROTO((ZVALUE z, long count));
  198. extern long zdigits MATH_PROTO((ZVALUE z1));
  199. extern FLAG zdigit MATH_PROTO((ZVALUE z1, long n));
  200. extern BOOL zsqrt MATH_PROTO((ZVALUE z1, ZVALUE *dest));
  201. extern void zroot MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *dest));
  202. extern BOOL zissquare MATH_PROTO((ZVALUE z));
  203. extern HASH zhash MATH_PROTO((ZVALUE z));
  204.  
  205. #if 0
  206. extern void zapprox MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res1, ZVALUE *res2));
  207. #endif
  208.  
  209.  
  210. #if 0
  211. extern void zmulmod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE z3, ZVALUE *res));
  212. extern void zsquaremod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  213. extern void zsubmod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE z3, ZVALUE *res));
  214. #endif
  215. extern void zminmod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE *res));
  216. extern BOOL zcmpmod MATH_PROTO((ZVALUE z1, ZVALUE z2, ZVALUE z3));
  217.  
  218.  
  219. /*
  220.  * These functions are for internal use only.
  221.  */
  222. extern void ztrim MATH_PROTO((ZVALUE *z));
  223. extern void zshiftr MATH_PROTO((ZVALUE z, long n));
  224. extern void zshiftl MATH_PROTO((ZVALUE z, long n));
  225. extern HALF *zalloctemp MATH_PROTO((LEN len));
  226. extern void initmasks MATH_PROTO((void));
  227.  
  228.  
  229. /*
  230.  * Modulo arithmetic definitions.
  231.  * Structure holding state of REDC initialization.
  232.  * Multiple instances of this structure can be used allowing
  233.  * calculations with more than one modulus at the same time.
  234.  * Len of zero means the structure is not initialized.
  235.  */
  236. typedef    struct {
  237.     LEN len;        /* number of words in binary modulus */
  238.     ZVALUE mod;        /* modulus REDC is computing with */
  239.     ZVALUE inv;        /* inverse of modulus in binary modulus */
  240.     ZVALUE one;        /* REDC format for the number 1 */
  241. } REDC;
  242.  
  243. extern REDC *zredcalloc MATH_PROTO((ZVALUE z1));
  244. extern void zredcfree MATH_PROTO((REDC *rp));
  245. extern void zredcencode MATH_PROTO((REDC *rp, ZVALUE z1, ZVALUE *res));
  246. extern void zredcdecode MATH_PROTO((REDC *rp, ZVALUE z1, ZVALUE *res));
  247. extern void zredcmul MATH_PROTO((REDC *rp, ZVALUE z1, ZVALUE z2, ZVALUE *res));
  248. extern void zredcsquare MATH_PROTO((REDC *rp, ZVALUE z1, ZVALUE *res));
  249. extern void zredcpower MATH_PROTO((REDC *rp, ZVALUE z1, ZVALUE z2, ZVALUE *res));
  250.  
  251.  
  252. /*
  253.  * macro expansions to speed this thing up
  254.  */
  255. #define ziseven(z)    (!(*(z).v & 01))
  256. #define zisodd(z)    (*(z).v & 01)
  257. #define ziszero(z)    ((*(z).v == 0) && ((z).len == 1))
  258. #define zisneg(z)    ((z).sign)
  259. #define zispos(z)    (((z).sign == 0) && (*(z).v || ((z).len > 1)))
  260. #define zisunit(z)    ((*(z).v == 1) && ((z).len == 1))
  261. #define zisone(z)    ((*(z).v == 1) && ((z).len == 1) && !(z).sign)
  262. #define zisnegone(z)    ((*(z).v == 1) && ((z).len == 1) && (z).sign)
  263. #define zistwo(z)    ((*(z).v == 2) && ((z).len == 1) && !(z).sign)
  264. #define zisleone(z)    ((*(z).v <= 1) && ((z).len == 1))
  265. #define zistiny(z)    ((z).len == 1)
  266. #define zissmall(z)    (((z).len < 2) || (((z).len == 2) && (((short)(z).v[1]) >= 0)))
  267. #define zisbig(z)    (((z).len > 2) || (((z).len == 2) && (((short)(z).v[1]) < 0)))
  268.  
  269. #define z1tol(z)    ((long)((z).v[0]))
  270. #define z2tol(z)    (((long)((z).v[0])) + \
  271.                 (((long)((z).v[1] & MAXHALF)) << BASEB))
  272. #define    zclearval(z)    memset((z).v, 0, (z).len * sizeof(HALF))
  273. #define    zcopyval(z1,z2)    memcpy((z2).v, (z1).v, (z1).len * sizeof(HALF))
  274. #define zquicktrim(z)    {if (((z).len > 1) && ((z).v[(z).len-1] == 0)) \
  275.                 (z).len--;}
  276. #define    zfree(z)    freeh((z).v)
  277.  
  278.  
  279. /*
  280.  * Output modes for numeric displays.
  281.  */
  282. #define MODE_DEFAULT    0
  283. #define MODE_FRAC    1
  284. #define MODE_INT    2
  285. #define MODE_REAL    3
  286. #define MODE_EXP    4
  287. #define MODE_HEX    5
  288. #define MODE_OCTAL    6
  289. #define MODE_BINARY    7
  290. #define MODE_MAX    7
  291.  
  292. #define MODE_INITIAL    MODE_REAL
  293.  
  294.  
  295. /*
  296.  * Output routines for either FILE handles or strings.
  297.  */
  298. extern void math_chr MATH_PROTO((int ch));
  299. extern void math_str MATH_PROTO((char *str));
  300. extern void math_fill MATH_PROTO((char *str, long width));
  301. extern void math_flush MATH_PROTO((void));
  302. extern void math_divertio MATH_PROTO((void));
  303. extern void math_cleardiversions MATH_PROTO((void));
  304. extern void math_setfp MATH_PROTO((FILE *fp));
  305. extern char *math_getdivertedio MATH_PROTO((void));
  306. extern int math_setmode MATH_PROTO((int mode));
  307. extern long math_setdigits MATH_PROTO((long digits));
  308.  
  309.  
  310. #ifdef VARARGS
  311. extern void math_fmt();
  312. #else
  313. extern void math_fmt MATH_PROTO((char *, ...));
  314. #endif
  315.  
  316.  
  317. /*
  318.  * The error routine.
  319.  */
  320. #ifdef VARARGS
  321. extern void math_error();
  322. #else
  323. extern void math_error MATH_PROTO((char *, ...));
  324. #endif
  325.  
  326.  
  327. /*
  328.  * constants used often by the arithmetic routines
  329.  */
  330. extern HALF _zeroval_[], _oneval_[], _twoval_[], _tenval_[];
  331. extern ZVALUE _zero_, _one_, _ten_;
  332.  
  333. extern BOOL _math_abort_;    /* nonzero to abort calculations */
  334. extern ZVALUE _tenpowers_[32];    /* table of 10^2^n */
  335. extern int _outmode_;        /* current output mode */
  336. extern LEN _mul2_;        /* size of number to use multiply algorithm 2 */
  337. extern LEN _sq2_;        /* size of number to use square algorithm 2 */
  338. extern LEN _pow2_;        /* size of modulus to use REDC for powers */
  339. extern LEN _redc2_;        /* size of modulus to use REDC algorithm 2 */
  340. extern HALF *bitmask;        /* bit rotation, norm 0 */
  341.  
  342. #endif
  343.  
  344. /* END CODE */
  345.